﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>

void PrintArray(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}

void _MergeSort(int* arr, int left, int right, int* tmp)
{
	if (left >= right) return;

	int mid = (right + left) / 2;
	// 分成[left,mid] [mid+1,right]两个区间
	_MergeSort(arr, left, mid, tmp);
	_MergeSort(arr, mid+1, right, tmp);
	 
	// 在对两个区间元素进行合并排序
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left; // 一定是left位置开始
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
			tmp[i++] = arr[begin1++];
		else
			tmp[i++] = arr[begin2++];
	}
	// 将多余的元素直接尾插到tmp(因为剩下的元素肯定都是在一个区间，是有序的)
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	// 这里的两个数组也要对齐，否则就会一直只覆盖数组前部分三
	memcpy(arr + left, tmp + left, (right - left + 1)*sizeof(int)); // 把tmp全部拷贝回原数组
}

void MergeSort(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);
	_MergeSort(arr, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

// 非递归
void MergeSortNonR(int* arr, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);

	// 记录每次要归并的数据个数
	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)// 将数组分成i块，每块区间gap个数据
		{	// [i,i+gap-1] [i+gap,i+2*gap-1]两个部分都是gap个数据
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2*gap - 1;
			
			// 第二组的都越界不存在，那么第二组不用归并了，跳出循环
			if (begin2 >= n)
				break;
			//第二组的begin2没越界，end2越界了，需要修正区间，再归并
			if (end2 >= n)
				end2 = n - 1;
			
			int j = i; // 每次都是i位置开始
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2])
					tmp[j++] = arr[begin1++];
				else
					tmp[j++] = arr[begin2++];
			}
			// 将多余的元素直接尾插到tmp(因为剩下的元素肯定都是在一个区间，是有序的)
			while (begin1 <= end1)
			{
				tmp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = arr[begin2++];
			}
			memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int));
		}
		gap *= 2; // 区间大小按二倍扩
	}
	free(tmp);
	tmp = NULL;
}


void testmergesort()
{
	int arr[] = { 12,13,11,10,9,7,8,4,5,6,1,3,2 };
	int n = sizeof(arr) / sizeof(int);
	PrintArray(arr, n);
	//MergeSort(arr, n);
	MergeSortNonR(arr, n);
	PrintArray(arr, n);
}
//int main()
//{
//	testmergesort();
//	return 0;
//}

// 创建随机数文件
void CreateData()
{
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt"; // 创建文本data.txt
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fin error");
		return;
	}
	for (int i = 0; i < n; i++)
	{
		int x = rand() + i;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}

// file1文件的数据和file2文件的数据归并到mfile文件中
void MergeFile(const char* file1, const char* file2, const char* mfile)
{
	// 先打开三个文件
	FILE* fout1 = fopen(file1, "r");
	if (fout1 == NULL)
	{
		perror("fopen file1 fail!");
		return;
	}
	FILE* fout2 = fopen(file2, "r");
	if (fout2 == NULL)
	{
		perror("fopen file2 fail!");
		return;
	}
	FILE* mfin = fopen(mfile, "w");
	if (mfin == NULL)
	{
		perror("fopen mfile fail!");
		return;
	}

	// 归并逻辑实现
	int x1 = 0;
	int x2 = 0;
	int ret1 = fscanf(fout1, "%d\n", &x1);
	int ret2 = fscanf(fout2, "%d\n", &x2);
	// EOF代表读到头了
	while (ret1 != EOF && ret2 != EOF)
	{
		if (x1 < x2)
		{
			fprintf(mfin, "%d\n", x1);
			ret1 = fscanf(fout1, "%d\n", &x1); // 还要取下一个的
		}
		else
		{
			fprintf(mfin, "%d\n", x2);
			ret2 = fscanf(fout2, "%d\n", &x2);
		}
	}
	while (ret1 != EOF)
	{
		fprintf(mfin, "%d\n", x1);
		ret1 = fscanf(fout1, "%d\n", &x1); // 还要取下一个的
	}
	while (ret2 != EOF)
	{
		fprintf(mfin, "%d\n", x2);
		ret2 = fscanf(fout2, "%d\n", &x2);
	}
	fclose(fout1);
	fclose(fout2);
	fclose(mfin);
}

// 调用qsort用的比较函数
int compare(const void* a, const void* b)
{
	return (*(int*)a - *(int*)b);
}
// 读取n个数的文件，将其在内存里排序好再写到文件里，返回读取到的数据个数，读不到数据了返回0
int ReadNNumSortToFile(FILE* fout, int* a, const char* file, int n)
{
	// 想写n个数据到内存里(实际是写了i个数据)
	int x = 0;
	int i = 0;
	while (i < n && fscanf(fout, "%d\n", &x) != EOF)
		a[i++] = x;// 用x取文件里的每个数据

	// 对内存中的数据排序
	qsort(a, n, sizeof(int), compare);

	// 打开文件
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen fail!");
		return 0;
	}
	// 将内存中数据写到文件
	for (int j = 0; j < n; j++)
	{
		fprintf(fin, "%d\n", a[j]);
	}
	fclose(fin);
	
	return i; // 返回读取到的数据个数
}


// MergeSortFile的第二个是每次取多少个数据到内存中排序，然后写到一个小文件进行归并
// 这个n给多少取决于我们有多少合理的内存可以利用，相对⽽言n越大，更多数据到内存中排序后，
// 再走文件归并排序，整体程序会越快⼀些。
void MergeSortFile(const char* file ,int n)
{
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fin error");
		return;
	}

	const char* file1 = "file1.txt";
	const char* file2 = "file2.txt";
	const char* mfile = "mfile.txt";

	// 把文件分成小部分,在内存中(a)排序好后，写到文件里
	int* a = (int*)malloc(sizeof(int) * n);
	if (a == NULL)
	{
		perror("mallo fail!");
		return;
	}
	ReadNNumSortToFile(fout, a, file1, n);
	ReadNNumSortToFile(fout, a, file2, n);

	while (1)
	{
		// 将file1和file2归并到mfile
		MergeFile(file1, file2,mfile);

		// 删除file1和file2
		if (remove(file1) != 0 || remove(file2) != 0)
		{
			perror("remove fail!");
			return;
		}
		// 给mfile改名为mfile
		if (rename(mfile, file1) != 0)
		{
			perror("rename fail!");
			return;
		}
		// 读取N个数据到file2，继续走归并
		// 如果一个数据都没读到，则归并结束了
		if (ReadNNumSortToFile(fout, a, file2, n) == 0)
			break;
	}
	fclose(fout);
	free(a);
}

int main()
{
	CreateData();
	MergeSortFile("data.txt", 10000);
	return 0;
}